COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0NGR25\M1BDJ25\M3NGR30\F3
C00004 ENDMK
C⊗;
\\M0NGR25;\M1BDJ25;\M3NGR30;\F3
\CCOMPUTER SCIENCE DEPARTMENT
\CSTANFORD UNIVERSITY





\CCS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1973
\CMIDTERM EXAM
\F0\COpen Books and Notes





\J	Write  LISP  functions  as  follows  using  the  M-expression
notation used in class:

	1. \F1commontail[u,v]\F0 is the longest common sublist of
\F1u\F0 and \F1v\F0 ending with the ends of the lists.  Thus
\F1commontail[\F0(A B C D E),(A C D E)] = (C D E).

	2. \F1permut u\F0 is a list of all the permutations of the
list \F1u\F0.  Thus

	\F1permut \F0(A B C) = ((A B C)(A C B)(B A C)(B C A)(C A B)(C B A)).

The order in which the permutations are listed is not important here.

	3. Devise a list structure representation of positions in the
game of tic-tac-toe (noughts and crosses), and write functions \F1ter p\F0,
which tells whether the game is over in position \F1p\F0,
\F1imval p\F0 which tells the value of the game for a terminated
position (use -1, 0 and 1 for values), and \F1successors p\F0 which
gives the successors to a non-terminating position \F1p\F0.  Make no
special effort to achieve efficiency.\.